from typing import Optional

from python.mypackage import TreeNode


class Solution:
    """
    方法： diameterOfBinaryTree 计算二叉树的直径(最长路径)
    
    Args:
        root (Optional[TreeNode]): 二叉树的根节点
        
    Returns:
        int: 二叉树中任意两个节点之间的最长路径长度
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(H)，其中 H 为二叉树的高度。递归调用的栈空间取决于二叉树的高度。
    """
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def depth(node):
            if not node:
                return -1
            # 左子树最大链长 + 1
            l_len = depth(node.left) + 1
            # 右子树最大链长 + 1
            r_len = depth(node.right) + 1
            # 计算最大链长
            nonlocal ans
            ans = max(ans, l_len + r_len)
            return max(l_len, r_len)
        depth(root)
        return ans

    